INTRODUCTION:

There are quite a number of multicast protocols for ad-hoc networks. Beginning in 1995 [15], many different approaches have been proposed. This section describes some characteristics that allow a classification of the protocols. In the following, the algorithms of existing protocols are outlined and classified into the previously defined classes [2].

1.1 Classification Characteristics:

1.1.1 Topology- vs. Position-based Protocols:

The classification of a routing protocol according to whether it is topology based or position-based depends on how the protocol calculates its routes. Routing decisions in ad-hoc networks are always based on neighbor relations in the network [1]. These relations can be used in two different ways.

Topology-based Protocols Topology-based protocols use the information about existing links between neighboring nodes to perform packet forwarding. This information can be seen as a topology graph of the network, and a routing algorithm in this context is a type of distributed graph algorithm that searches a path from a source to a destination node. Principally, a route has to be discovered prior to starting the actual packet transmission. Local topology information alone does not give any hints on which of the neighboring nodes a packet should be sent to—unless one of the neighboring nodes is the destination itself. This introduces a potential delay for packets that should be sent before any routes have been discovered. Furthermore, if a link within a previously discovered route breaks due to topological changes caused by node movement or radio fluctuations, the corresponding route has to be repaired, or a new route has to be found. Position-based Protocols Position-based protocols make use of physical node positions to overcome the drawbacks of topology-based approaches. These protocols require the participating nodes to be aware of their geographic positions. This can be accomplished by means of GPS [10] or some GPS-free technique [12], especially for indoor scenarios [8, 10]. Position-based protocols do not rely on discovering routes that are used for all subsequent packets; instead, they perform forwarding on a hop-by-hop basis. Packets are routed by means of the current node’s position, the neighbors’ positions and the destination’s position. This position information is sufficient to decide which next hop should receive a packet. In Greedy Forwarding, one form of position based routing, nodes periodically exchange beacon messages containing their own position. In this way, every node is able to build a table containing information on all its neighboring nodes within radio range. If a node wants to send a packet, it compares the distances of all its neighbors to the desired destination and picks the neighbor closest to the destination. Sending the packet to this neighbor will yield the maximum progress towards the destination. Hop by hop, the packet will be forwarded and eventually reach its final destination. While a node’s own position can be obtained by positioning services and the neighbors’ position by means of beaconing, the position of the destination can be provided by a Location Service. There are a number of algorithms for location services. A straight-forward one is the Reactive Location Service (RLS) [17]. It works as follows: The querying node creates a request packet including its own position as the source address and the ID of the destination. It then broadcasts the packet to all its neighbors in radio range. Each of them again broadcasts the packet. To avoid that the packet circulates in the network forever, a node receiving the same packet for the second time simply discards it. The re-broadcasting of a received packet is delayed for a random back off time in order to sidestep the broadcast storm problem [12] that is caused by collisions of packets simultaneously rebroadcast by different forwarders. Eventually, the destination node receives the request packet and creates a response packet. This response contains the inquired position as source address and the ID and position of the querying node, which were contained in the query packet, as destination. This response packet is then sent back to the querying node using position based unicast as described above. One problem that can occur with position-based routing is the existence of voids, i. e., regions where no node is located, so that packets reach a local optimum on their way to the destination. Figure 1 shows such a case. A packet that is on its way from node S to node D gets stuck when it reaches node A. There is no node that is located within radio range r to A and at the same time located closer to D. In order to get out of such a local optimum, the packet has to accept the loss of some progress before it can proceed again. For these cases, a variety of Recovery Strategies exists that are employed whenever a greedy routing algorithm gets stuck.

1.1.2 Tree vs. Mesh Structure Tree-based Protocols:

Tree-based multicast protocols are characterized by the property that they construct a tree for the distribution of data packets. Each node that is part of such a tree has its well-defined successors—unless it is a leaf node. Should part of a tree be affected by topological changes within the network, a tree reconstruction is required. Tree reconstructions may be performed globally or locally. While a global reconstruction means that the currently used tree is discarded and a new one is built, a local reconstruction is more sophisticated. It defines additional protocol elements that allow reconnection of a tree at the point where it broke. The benefit of this behavior is that the communication overhead induced by the repair procedure can be kept to a minimum. Delivery trees can be classified into two categories: source-specific trees and shared trees. A source-specific tree is a tree that is rooted at a specific source and that is used only to distribute packets generated by this source. All other sources have to build and maintain their own trees for their packets. Special kind of source-specific trees are those based on a rendezvous point. In these trees it is not the source that is the root of the tree but a rendezvous point (RP). The RP maintains the tree paths to all receivers of its group and handles all packets that are sent to the group. A source that wants to deliver a multicast packet sends its packet to the closest rendezvous point, which then feeds the packet into the delivery tree. The second category, shared tree-based protocols, uses a single tree per multicast group. Each node is root for its own packets and at the same time tree node for the packets of the other nodes. This reduces management overhead for the case that at least some of the nodes simultaneously act as senders and receivers in the group. The first proposals of multicast routing protocols for mobile ad-hoc networks were tree-based approaches based on existing multicast protocols for wired networks like PIM-SM [16] (current RFC: [15]). In 1995, [50] described Reservation-Based Multicast, the first multicast protocol for mobile networks.

Figure 1 : Local optimum in greedy forwarding

Mesh-based Protocols:

Mesh-based protocols follow a different approach. A mesh of forwarding routers is used to disseminate the data packets. Every node that is part of the mesh can have multiple incoming and outgoing links, i. e., entries in a forwarding table. Whenever a packet arrives at one of the in-going links, it is forwarded to every outgoing link. On the one hand, a mesh is more robust to topology changes than a tree because it can provide more than one path from a source to each of its destinations. On the other hand, meshes imply an increased overhead for this very reason.

1.1.3 Centralized vs. Decentralized Organization:

Regardless of whether designing a tree-based protocol or a mesh-based protocol, the organization of the group management and the data distribution may be done in a centralized or decentralized fashion.

Centralized Organization:

Centralized organization means that there is at least one node that acts as a so-called core. It is responsible for maintaining the group memberships or for taking care of the data dissemination. In tree-based protocols, e. g., the rendezvous point is a core for the data dissemination, and every data packet is routed to this rendezvous point before it is sent to the tree of recipients.

Decentralized Organization:

Decentralized approaches try to coordinate the nodes in a distributed manner. This means that senders and receivers contact each other directly in order to build up the required data distribution structure. Which of the two, sender or receiver, actually initiates the contact is determined by the

Specific protocol.

1.1.4 Sender Vs. Receiver Initiation:

As mentioned, there are two alternative ways in which a protocol can handle the initiation of a multicast session.

Sender Initiation:

A sender initiated session starts with a node that is willing to send data packets to a multicast group. It announces the start of a new session to the nodes in the network and invites them to join the group. After all nodes have subscribed, the source is able to use the session and send packets to the group.

Receiver Initiation:

The second alternative is receiver initiated sessions. In this case, receivers announce their subscription to certain multicast groups to all nodes in the network. Accordingly, data sources are able to start sending packets immediately once these are generated by the application, since group memberships are maintained independently of existing sources, and receiver nodes have already subscribed to the group.

2. Over View of Multicast Routing Protocol:

2.1 Distance Vector Multicast Routing Protocol (DVMRP):

DVMRP, the most predominant routing protocol on the MBONE specified in [4], builds source-based multicast delivery trees dynamically using a variant of the Reverse Path Forwarding algorithm. When a packet arrives on an interface, the reverse path to the source of the datagram is determined by examining a unicast routing table of known source networks. If the packet arrives on an interface that would be used to transmit unicast packets back to the source, then it is forwarded out of all interfaces that are part of tree. Otherwise, it is considered not to be on the optimal delivery tree and the packet is discarded. To minimize the number of branches necessary to reach all group members, outgoing interfaces are pruned from a tree if they have no members directly attached to it by sending a <source, group> pair Prune message. Tree branches are added dynamically as new members join the multicast group by grafting the new sections onto the delivery trees using a Graft message. DVMRP uses IP-IP encapsulation to traverse regions (tunnels) that do not support native multicast routing. Tunneling is done by encapsulating IP multicast packets in unicast IP packets and addressing them to routers that support native multicast routing. Neighbor DVMRP routers are discovered dynamically by periodically sending Neighbor Probe messages on local multicast capable network interfaces and tunnel pseudo interfaces. To prevent these messages from propagating beyond a subnetwork, they are sent to the All-DVMRP-Routers IP multicast address. Each probe message contains a list of Neighbor DVMRP routers for which the probe message has been received so as to ensure that routers know of each other’s existence. Furthermore, to ensure a consistent view of the unicast path back to a source, a unicast routing table is propagated to all DVMRP routers as an integral part of the protocol. Although this introduces additional overhead, it removes the burden of synchronization from the network manager and places it on the protocol thereby reducing the risk of creating routing loops or black hosts due to disagreement between neighbor routers on the upstream interface. A major disadvantage of this type of protocol is that it does not scale well since multicast routers must maintain state per group per active source. More- over, because prune messages have to be sent for leaf routers with no attached group members, this algorithm is not suitable for sparsely populated group members typical of most wide area networks, and would saturate links with control messages.

2.2 Multicast Open Shortest Path First (MOSPF):

MOSPF specified in [5] is built on top of OSPF [6], a unicast link state routing protocol, to provide multicast routing capability. Routers running MOSPF periodically collect reach ability and group membership information and flood it in link state packets, to compute the delivery tree. On receiving a multicast packet, each router uses membership and topology information to calculate the shortest path tree routed at the next hop router of the source of the packet, hence it is source-based. If a router falls within a computed tree, it forwards the packet over the interfaces defined by the calculation. Otherwise, packet is dropped. MOSPF routers maintain a current image of the network topology through the unicast OSPF routing tables. Within a subnetwork, a single MOSPF router, denoted the Designated Router (DR), is assigned the responsibility of maintaining a list of directly attached group members and communicating it to all other routers in the OSPF area using Group-Membership Link State Advertisements (LSAs). The DR sends a separate Group-Membership LSA for each multicast group having one or more entities in the DR's local group database which is flooded only within a single area.

The shortest path tree is built on demand when a router receives the first multicast packet for a particular <source, group> pair by using the Routers-LSAs and Network-LSAs (see [6]) in the MOSPF link state database to construct a source-rooted shortest-path tree using Dijkstra's algorithm. Group-Membership LSAs are then used to prune those branches that do not lead to sub networks containing individual group members. Each MOSPF router that is in the delivery path determines its position within the tree and creates a forwarding cache entry containing the <source, group> pair, the upstream node, and the downstream interfaces. The forwarding cache entry is then used to forward all subsequent packets for the <source, group> pair and is updated only if the topology of the OSPF internetwork changes or if there is a change in Group-Membership LSAs indicating that distribution of individual groups has changed. Unlike DVMRP, MOSPF does not provide support tunnels. In addition to the scalability problems due to its source-based nature, flooding of group membership and reachability information may cause a considerable increase in link traffic. The computation cost of the shortest path tree for each source using methods such as Dijkstra's calculation may also be too high.

2.3 Core-based Trees (CBT) Protocol

CBT protocol uses a set of pre-nominated routers called cores to establish a shared multicast delivery tree through an explicit message protocol specified in [7] and [8]. Multicast trees for each group consist of a primary core, secondary cores, and non-core routers. Tree construction is triggered by the receipt of an IGMP report by a CBT capable router, which then sends a join message towards a target core using the next hop address from the unicast routing table. The join request is processed by all intermediate routers that mark the interface on which the join was received as belonging to the group's delivery tree. On receipt of a join message, the core replies with an acknowledgment (ACK) message which traverses the reverse path of the corresponding join to the sending router. On a subnet with multiple multicast routers, the subnet's IGMP querier is designated the CBT-DR for joining trees on behalf of member hosts. If before reaching the core the message comes across a router which is al- ready on the tree, that router takes up the responsibility of acknowledging the message. When the source router of the join message receives an ACK message, it creates a CBT Forwarding Information Base (FIB) entry, listing the interfaces corresponding to a particular group over which multicast packets should be for- warded. Thus when a packet is received, it is forwarded out of all interfaces dictated by the FIB. Figure 2 illustrates how an incoming packet traverses a CBT multicast delivery tree. CBT operates under two forwarding modes. In native mode, when a CBT router receives a data packet, the packet may only be forwarded over outgoing tree interfaces if and only if it has been received via a valid on-tree interface or the packet has arrived encapsulated from a non-member. On the other hand in CBT mode, routers ignore all non-locally originated multicast data packets. Locally- originated packets are forwarded native mode by the DR, TTL 1, over outgoing member subnets for which that router is DR. Additionally, the DR encapsulates the packets and then forwards them over all tree interfaces specified in the CBT FIB entry. Certainly, a major disadvantage of this protocol would be the traffic concentration on the shared path since all packets for that group traverse the same link. However, a great advantage of CBT is that it totally supports non-member sending of multicast packets. Sources that are not members of a multicast group encapsulate packets and then send them towards the core of the tree. If the encapsulated packet hits the tree at an on-tree router, the packet is forwarded as dictated by the FIB entries.

Figure 2: CBT packet forwarding

2.4 Protocol Independent Multicast (PIM):

PIM, as the name suggests, builds a multicast routing tree that uses unicast routing information independent of the particular unicast routing protocol de- ployed. PIM operates in two modes, Dense-mode and Sparse-mode described in [9], [10] and [11]. PIM Dense-mode (DM) is designed to work in environ- ments where multicast group members are densely populated and bandwidth is abundant. PIM Sparse-mode (SM) is designed to support multicast groups with members that are sparsely distributed across many regions and bandwidth is not necessarily widely available. The motivation for developing PIM was that existing multicast protocols are specifically developed for either densely populated regions (e.g. DVMRP or MOSPF) or sparsely populated regions (e.g. CBT), but not both. PIM-DM uses the Reverse Path Multicasting (RPM) algorithm, but unlike DVMRP, multicast packets are forwarded downstream until explicit prune or truncation messages are received. The designer’s traded-of packet duplication for routing protocol independence and less overhead in building a parent/child database as is done in DVMRP. PIM-SM requires routers with directly attached downstream members to join a sparse-mode distribution tree by transmitting explicit join messages to the group's primary Rendezvous Point (RP) which acts as the root of the tree. PIM- SM operates very much like CBT where a Designated Router (DR) upon receipt of an IGMP group report, sends a join/prune message towards the designated RP for the group. Each router along the path toward the RP builds a <anysource, group> state for the group before forwarding the request. This state creates a shared, RP-centered distribution tree that reaches all group members.

Figure 3. Multicast Transport Architecture

III – Multicast Architecture:

3.1 ASSM:

The first module is a multicast state setup protocol, Ad hoc State Setup Multicast Protocol (ASSM). This protocol is used for setting up the multicast forwarding state from a receiver along a branch of the multicast tree and establishing transport state at each hop. To find the path from a receiver to the rest of the tree, ASSM uses the route to the multicast source that is provided by the unicast routing protocol. Traditionally, multicast protocols discover their own routes using a network-wide broadcast, where a route discovery packet is sent to each node in the network. By using routes that are already present in the unicast routing table, ASSM can greatly reduce its overhead. The operation of ASSM is show in Figure3, where a new HCP receiver sends an ASSM Join message to join a multicast tree. When an intermediate node (or the source itself) receives an ASSM Join, it establishes multicast forwarding state for the new branch. After that, ASSM passes the Join packet to the HCP layer, which establishes transport state. Whenever the Join message reaches an existing node on the tree, the Join message may be suppressed if there is no need to send it upstream towards the source. Another interaction between ASSM and HCP is to carry information about missed packets. After the multicast and transport state is established, the source transmits data for the receivers. However, due to several reasons, receivers might miss some of these packets. An HCP receiver periodically resends the ASSM Join both to refresh the forwarding state and to inform upstream nodes about any lost packets. The receiver builds a list of missed packets and includes this list in the Join message. As the Join message travels to upstream nodes, each node checks if it has some of these missed packets in its application buffer; if it does, then it queues those packets for retransmission(figure no 4) . Any time a node has those missing packets and queues them for retransmission, then that node deletes those packets from the Join message so that its own upstream nodes avoid a duplicate retransmission. Ultimately the Join message reaches the source; the source retransmits whatever packets remain in the list.

Figure 4. ASSM assists an HCP Receiver to join the multicast tree

3.2 MDA:

The second module is a Mobility Detection Algorithm (MDA), which enables the multicast architecture to determine the cause of packet loss and react properly. A link break is typically detected by the MAC layer, when it fails to send a frame after trying for a certain number of times. The MAC layer propagates this failure notification to the routing layer. When a routing protocol receives this information, it usually makes an assumption that the cause of the lost packet must be mobility. However, this assumption is not always correct, since packets may get dropped due to collision or congestion. Making this faulty assumption comes with a price; routing protocols making this mistake suffer from significant overhead when they initiate the repair of routes that have not been broken, resulting in decreased throughput for affected applications(figure no 5).

Figure 5 MDA: Link Break Due to Mobility

We have designed this cross-layer MDA to detect the cause of a lost packet. When ASSM sends a Join message and the MAC layer reports a link break, ASSM first consults with MDA; new routes are discovered only when MDA indicates that the current route is truly broken (Figure 4.3). However, if the packet loss is due to ongoing congestion, MDA does not confirm the link break and ASSM does not trigger any route repair activity (Figure 6).

Figure 6 MDA: False Link Break Due to Congestion

3.3 HCP:

The third module is a hop-by-hop congestion control (HCP) algorithm, which provides reliable transmission and congestion control at each hop in the multicast tree. Nodes in the tree buffer packets so they can retransmit them if needed. One of the main goals of HCP is to be able to send faster to those receivers who have more bandwidth, while still accommodating slower receivers. Further, by design HCP uses application layer buffering since an application layer can typically access the disk space and is not constrained by the sizes of buffer space available at the transport layer (Figure 7). When a sender or a receiver application is started, it initializes by allocating a prespecified amount of disk space. A forwarder also has access to a buffer on disk and when a forwarding state is set, it also calls an initialization and allocates from this buffer. HCP achieves reliability in two phases. In the first phase, each node in the tree chooses one of its children and sends data to it reliably, using the MAC layer. Other children try to receive the packet by listening to this transmission. However, this kind of snooping is not completely reliable, so some children may lose some packets. To cope with this loss, HCP uses a second phase of end-to-end reliability. Each receiver keeps track of all the packets it has received, and if it misses any packet, it asks its upstream nodes to resend those packets. This request is added to the periodic ASSM Join message. HCP stores recent packets in its application buffer; when it receives a request for retransmission, it pulls that packet from the application buffer and schedules it for transmission by queuing the packet in its retransmission queue (Figure 8). Next time, when a packet is transmitted, HCP uses packet from its retransmission queue, removes the packet from this queue, and then retransmits it. Besides reliability, HCP also provides a congestion control algorithm which estimates the correct sending rate. Congestion control takes help from an internal module: a Scheduler that maintains information about all the flows passing through the node. The scheduler uses a fair policy and sends data to each flow by taking turns. The correct sending rate depends upon MAC layer; whenever MAC layer transmits a frame, it informs HCP and HCP queues its next packet. HCP also uses flow-control, which avoids sending data to a downstream node, if the buffer at the downstream node is full. This mechanism is also achieved by snooping. When a downstream node forwards data to its own downstream node, then it updates a field reserved for available buffer in the HCP packet; the upstream node snoops at the HCP packet and comes to know about the available buffer at its downstream node. Data is forwarded to that neighbor, only when that the buffer becomes available at that neighbor.

Figure 7 Forwarding of a new packet

Figure 8 HCP: Retransmission of a lost packet

REFERENCES:

1. I. Chlamtac, M. Conti, and J. Liu, “Mobile Ad Hoc Networking: Imperatives and Challenges,” in Ad Hoc Networks 1 pp. 13-64, 2003.

2. K. Tang, K. Obraczka, S.-J. Lee, and M. Gerla, “A Reliable, Congestion- Controlled Multicast Transport Protocol in Multimedia Multi-hop Networks,” 5th International Symposium on Wireless Personal Multimedia Communications, pp. 252–256, Oct, 2002.

3. Venkatesh Rajendran, Katia Obraczka, Yunjung Yi, Sung-Ju Lee, Ken Tang, and Mario Gerla, “Combining Source and Localized Recovery to Achieve Reliable Multicast in Multi-Hop Ad Hoc Networks,” in IFIP-TC6 Networking Conference, May, 2004, pp. 112–124.

4. Yang-Hua Chu, Sanjay G. Rao, and Hui Zhang, “A case for End System Multicast,” in Measurement and Modeling of Computer Systems, 2000, pp. 1–12.

5. Chao Gui and Prasant Mohapatra, “Efficient Overlay Multicast for Mobile Ad Hoc Networks,” in IEEE Wireless Communications and Networking Conference (WCNC), March 2003.

6. Yung Yi and Sanjay Shakkottai, “Hop-by-hop Congestion Control over a Wireless Multi-hop Network,” in IEEE INFOCOM, 2004.

7. D. Waitzman, C. Partridge, and S. Deering, “Distance Vector Multicast Routing Protocol,” RFC 1075, November 1988, http://www.rfceditor. org/rfc/rfc1075.txt.

8. S. Lee, W. Su, and M. Gerla, “On-Demand Multicast Routing Protocol in Multihop Wireless Mobile Networks,” in ACM/Baltzer Mobile Networks and Applications, special issue on Multipoint Communication in Wireless Mobile Networks, 2000.

9. Manoj Pandey and Daniel Zappala, “A Scenario Based Evaluation of Ad Hoc Multicast Routing Protocols,” in IEEE International Symposium on World of Wireless, Mobile and Multimedia Networks (WoWMoM), Italy, June 2005.

10. J. Jetcheva and D.B. Johnson, “Adaptive Demand-Driven Multicast Routing in Multi-Hop Wireless Ad Hoc Networks,” in ACM MOBIHOC, October 2001.

11. E.M. Royer and C.E. Perkins, “Multicast Operation of the Ad-Hoc On-Demand Distance Vector Routing Protocol,” in Mobile Computing and Networking, 1999.

12. C.E. Perkins and E.M. Royer, “Ad Hoc On Demand Distance Vector (AODV) Algorithm,” in IEEE Workshop on Mobile Computing Systems and Applications, 1999.

13. A. Adams, Jonathan Nicholas, and William Siadak, “Protocol Independent Multicast-Dense Mode (PIM-DM): Protocol Specification (Revised),” Sep 2003, Internet Draft (Work in Progress), draft-ietf-pim-dm-new-v2-04.txt.

14. S. Deering, Deborah Estrin, Dino Farinacci, Van Jacobson, Chinggung Liu, and Liming Wei, “Protocol Independent Multicast-Sparse Mode (PIM-SM): Motivation and Architecture,” Oct 1996, Internet Draft (Work in Progress),draft-ietf-idmr-pim-arch-01.psDraft.

15. D.B. Johnson and D.A. Maltz, “Dynamic Source Routing in Ad Hoc Wireless Networks,” in Mobile Computing, Imielinski and Korth, Eds., vol. 353. Kluwer Academic Publishers, 1996.

16. Lap Kong Law, Srikanth V. Krishnamurthy and Michalis Faloutsos, “fireworks: an adaptive group communication protocol for ad hoc networks”, Lecture Notes in Computer Science, Springer, Volume 3462/2005, pp: 853-868, ISBN: 978-3-540-25809-4

17. Younghwan Choi Bongsoo Kim Kwansoo Jung Hochoong Cho Sang-Ha Kim , “An Overlay Multicast Mechanism Using Single Hop clustering and tree division for mobile ad hoc networks”, Vehicular Technology Conference, 2006. VTC 2006-Spring. Volume: 2, On page(s): 921-926, ISBN: 0-7803-9392-9

18. Jane Yang Yu, Peter Han Joo Chong , “An efficient clustering scheme for large and dense mobile ad hoc networks”, Computer communications ISSN 0140-3664 , vol. 30, no1, pp. 5-16 , Elsevier Science, 06.

19. Blodt, S., “Efficient End System Multicast for Mobile Ad Hoc Networks”, Proceedings of the Second IEEE Annual Conference on Pervasive Computing and Communications Workshops (PERCOMW’04).

Received on 29.06.2011 Accepted on 06.07.2011

Research J. Engineering and Tech. 2(3): July-Sept. 2011 page 172-178